1.Field of the Invention
The present invention relates to an error correction code (ECC) circuit, and more particularly, to an ECC circuit with reduced hardware complexity.
2.Description of the Prior Art
An error correction code (ECC) has been widely used to prevent digital data from being affected by noise interference. For example, the error correction code such as a well-known Reed-Solomon code is applied to a broad spectrum of fields. Digital communication systems such as a mobile communication system, and a satellite communication system, as well as digital data storage devices such as the optical disk use the error correction code to confirm accuracy of the transmitted data and to correct error bits of the transmitted data. Please refer to FIG. 1, which is a prior art error correction system 10. The error correction system 10 includes an encoder 14 used to convert an input data 12 into a corresponding code word 16 according to a Reed-Solomon algorithm. The Reed-Solomon algorithm processes the input data 12 block by block. For example, RS(n,k) represents that the code word 16 has n symbols, and the input data 12 has k symbols wherein each symbol has m bits. The encoder 14 generates the ECC that has (n−k) symbols according to the input data 12. The calculated ECC is annexed to the input data 12 to form the code word 16. The ECC is calculated in a Galois field. For example, the ECC is generated according to GF(2m). A writing unit 18 is then used to record the code word 16 in a storage unit 20. A reading unit 22 is used to retrieve the code word 16 stored on the storage unit 20 and then transmits the retrieved code word 16 to a decoder 24 for converting the code word 16 into the original input data 12. The decoder 24 has a syndrome generator 26, a polynomial generator 28, an error locating circuit 30, an error value calculator 32, and an error correcting circuit 34. The syndrome generator 26 is used to check whether the code word 16 contains error bits, and then generates a syndrome corresponding to the code word 16. Based on the syndrome, the polynomial generator 28 applies a prior art Euclidean algorithm or a prior art Berlekamp-Massey algorithm to calculate an error value polynomial and an error location polynomial. According to the error location polynomial, the error locating circuit 30 applies a Chien search to calculate locations of the error bits. The error value calculator 32 then calculates error values corresponding to the error bits according to the locations of the error bits, the error value polynomial, and the error location polynomial. In the end, the error correcting circuit 34 uses the error values and related locations of the error bits to correct the error bits.
Please refer to FIG. 2, FIG. 3, and FIG. 4. FIG. 2 is a circuit diagram of the encoder 14 shown in FIG. 1. FIG. 3 is a circuit diagram of the syndrome generator 26 shown in FIG. 1. FIG. 4 is a circuit diagram of the error locating circuit 30 shown in FIG. 1. With regard to the encoder 14, the encoder 14 has a plurality of registers 36, a plurality of multipliers 38, and a plurality of adders 40. The prior art Reed-Solomon algorithm uses a generator polynomial G(x) to process the input data 12. Each multiplier 38 individually corresponds to one of the coefficients of the generator polynomial G(x), and is used to perform multiplication on the input data 12 with the corresponding coefficient. The adder 40 is used to perform addition on the multiplication result outputted from the multiplier 38 and the data stored in the register 36 preceding the adder 40, and stores addition result in the register 36 following the adder 40. It is noteworthy that the adder 40 performs an exclusive OR (XOR) logic operation in the Galois field. When the input data 12 has been inputted into the encoder 14 symbol by symbol, the register 36 stores the error correction code of the input data 12. Finally, the input data 12 and data stored in the register 36 are added by the adder 40 to generate the code word 16. With regard to the syndrome generator 26, the syndrome generator 26 also has a plurality of adders 40, a plurality of multipliers 38, and a plurality of registers 36. According to the prior art Reed-Solomon algorithm, the code word 16 with no error bit should be divided by the generator polynomial G(x) with the remainder equal to 0. If each symbol has 8 bits, the code word 16 corresponds to a polynomial R(x) having a degree of n, the input data 12 corresponds to a polynomial I (x), and the generator polynomial G(x) has a degree of k, the polynomial R(x) corresponds to the following equation.R(x)=Q(x)*G(x)=I(x)·Xn−k+r(x)=I(x)·Xn−k+I(x)·mod·G(x)
The “mod” shown in the above equation stands for a modulo division. The degree of the generator polynomial G(x) is n, that is, the generator polynomial G(x) corresponds to n roots. The generator polynomial G(x) is represented by the following equation.
            G      ⁡              (        x        )              =                  ∏                  i          =          0                          π          -          1                    ⁢                          ⁢              (                  x          -                      α            i                          )              ,where αi corresponds to an element in the Galois field GF(28).
Therefore, when each root αi is applied to the above equation, the remainder is equal to 0. However, if the code word 16 contains error data E(x), the polynomial R(x) becomes the following equation.R(x)=Q(x)*G(x)+E(x)
It is obvious that if each root αi is applied to the above equation, the remainder corresponding to each root will not be equal to 0. The remainder corresponding to the root αi becomes a syndrome corresponding to the root αi. Each symbol of the code word 16 is sequentially inputted into the syndrome generator 26. The adder 40 performs Galois field addition, and stores result in the register 36. Each multiplier 38 individually corresponds to one root αi of the generator polynomial G(x), and is used to perform Galois field multiplication on the data stored in the register 36 according to the corresponding αi. Then, the Galois field addition is performed on the result of the multiplier 38 with the following symbol of the code word 16. The above operation is repeated until each symbol of the code word 16 has been processed. At this time, each register 36 stores one symbol of the code word 16. If each symbol is equal to 0, there is no error bit in the code word 16. After the syndrome generator 26 has finished calculating the syndromes, the polynomial generator 28 shown in FIG. 1 continues calculating an error location polynomial P(x).P(x)=Cm*Xm+Cm−1*Xm−1+. . . . . . +1,2*m=k
The error locating circuit 30 is capable of calculating locations of the error bits according to the coefficients of the error location polynomial P(x) and the prior art Chien search algorithm. The error locating circuit 30 has a plurality of adders 40, a plurality of multipliers 38, and a plurality of registers 36. In the beginning, each register 36 individually stores a coefficient of the error location polynomial P(x) as an initial value, and each multiplier 38 individually corresponds to αm, αm−1, . . . . . . , α1. Each multiplier 38 performs a Galois field multiplication on data stored in a corresponding register 36, and the multiplication result updates the corresponding register 36. Finally, the data stored in each register 36 are added together by adders 40 to determine whether the addition result is a predetermined value (1 or 0 for example). Therefore, the error locating circuit 30 can find out which symbol in the code word 16 is erroneous. The above-mentioned encoder 14, syndrome generator 26, and the error locating circuit 30 have been widely used in handling error correction codes. The detailed operating principles and algorithms are not related to the primary objective of the present invention, and the lengthy description for the well-known operating principles and algorithms is skipped for simplicity.
Because the ECC is calculated in the Galois field, either the encoder 14 or the decoder 24 has to apply the Galois field addition and Galois field multiplication to an input data to generate the corresponding ECC. Therefore, the multipliers 38 and the adders 40 shown in FIG. 3 and FIG. 4 are necessary for both of the encoder 14 and the decoder 24. A prior art ECC circuit has been disclosed to use the same multipliers and adders in different circuits to perform different functions. For example, the U.S. Pat. No. 4,584,686 “REED-SOLOMON ERROR CORRECTION APPARATUS” has disclosed an ECC circuit that integrates the encoder 14 and the syndrome generator 26 shown in FIG. 1. The encoder 14 and the syndrome generator 26 share the same registers, multipliers, and adders to economize the use of actual hardware and to lower production cost. However, the prior art ECC circuit still requires a plurality of multipliers. The hardware of the multiplier is more complex than that of the adder, and the power consumption of the multiplier is greater than that of the adder. Therefore, the prior art ECC has a large size and consumes a great amount of power owing to the multipliers. In addition, the production cost is increased because of the multipliers.